1954E - Chain Reaction - CodeForces Solution

def bruteforce_solve(n, a):
    m = max(a)
    ans = [0] * m
    for k in range(1, m + 1):
                        b = a.copy()
        dead = 0
        while dead < n:
            carry = False
            for i in range(n):
                if b[i] > 0:
                    if not carry:
                        ans[k - 1] += 1
                        carry = True
                    b[i] -= k
                    if b[i] <= 0:
                        dead += 1
                else:
                    carry = False
    return ans


def solve(n, a):
                                        
    m = max(a)
    ans = [0] * m
    for k in range(1, m + 1):
        ans[k - 1] += ceil(a[0] / k)
    diff_arr = [0] * (m + 2)
    for i in range(1, n):
        l, r = a[i - 1], a[i]
        if l < r:
                        diff_arr[l] += 1
            diff_arr[r] -= 1
    divisors = [[] for _ in range(m + 1)]
    for d in range(1, m + 1):
        for mul in range(d, m + 1, d):
            divisors[mul].append(d)
    
    in_ranges_cnt = 0
    for i in range(m + 1):
        in_ranges_cnt += diff_arr[i]
        for k in divisors[i]:
            ans[k - 1] += in_ranges_cnt
    return ans


def test():

    from random import randint
    n = 10
    for _ in range(100):
        a = [randint(1, n) for __ in range(n)]
        ans = solve(n, a)
        bfans = bruteforce_solve(n, a)
        if ans != bfans:
            print(f'a={a} ans={ans} bfans={bfans}')
            raise Exception
    return


def main():

            
    n = int(input())
    a = readIntArr()
        ans = solve(n, a)
    oneLineArrayPrint(ans)

    return

import sys
input=sys.stdin.buffer.readline  
def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
 
def makeArr(defaultValFactory,dimensionArr):     dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
 
inf=float('inf')
 
from math import gcd,floor,ceil
import math
 
for _abc in range(1):
    main()